package leetcode.editor.cn;

public class P2424LongestUploadedPrefix {
    public static void main(String[] args) {
        LUPrefix solution = new P2424LongestUploadedPrefix().new LUPrefix(4);
        solution.upload(3);
        solution.upload(1);
        System.out.println(solution.longest());
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class LUPrefix {

        int[] u;
        boolean[] add;
        int n;

        public LUPrefix(int n) {
            this.n = n;
            u = new int[n + 1];
            for (int i = 0; i < u.length; i++) {
                u[i] = i;
            }
            add = new boolean[n + 1];
            add[0] = true;
        }

        public void upload(int video) {
            add[video] = true;
            if (add[video - 1]) {
                union(video - 1, video);
            }
            if (video < n && add[video + 1]) {
                union(video, video + 1);
            }
        }

        private void union(int l, int r) {
            u[l] = find(r);
        }

        public int longest() {
            return find(0);
        }

        private int find(int i) {
            if (u[i] != i) {
                u[i] = find(u[i]);
            }
            return u[i];
        }


    }

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix obj = new LUPrefix(n);
 * obj.upload(video);
 * int param_2 = obj.longest();
 */
//leetcode submit region end(Prohibit modification and deletion)

}